package com.lwl.Algorithmic_data_structure.class12二叉树;

import com.lwl.Utils.MyTreeNode;

/**
 * @author lwl
 * @Description 给出树中两个节点a，b，求这两个节点的最低公共祖先
 * @date 2023/6/1 9:34
 */
public class Code07getLeastCommonAncestors {

    class Info {

        boolean containA;

        boolean containB;

        MyTreeNode lca;

        public Info(boolean containA, boolean containB, MyTreeNode lca) {
            this.containA = containA;
            this.containB = containB;
            this.lca = lca;
        }
    }

    public MyTreeNode a = null;

    public MyTreeNode b = null;

    public MyTreeNode getLeastCommonAncestors(MyTreeNode head, MyTreeNode a, MyTreeNode b) {
        this.a = a;
        this.b = b;
        return process(head).lca;
    }

    public Info process(MyTreeNode head) {
        if (head == null) {
            return new Info(false, false, null);
        }

        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);

        boolean containA = leftInfo.containA || rightInfo.containA || head == a;
        boolean containB = leftInfo.containB || rightInfo.containB || head == b;
        MyTreeNode lca = null;
        // lca 不可能既在左，又在右的
        if (leftInfo.lca != null || rightInfo.lca != null) {
            lca = leftInfo.lca == null ? rightInfo.lca : leftInfo.lca;
        }
        // 只有左右节点都没有lca的时候，才有机会轮到当前节点
        if (lca == null) {
            if (containA & containB) {
                lca = head;
            }
        }
        return new Info(containA, containB, lca);
    }
}
